/*
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
*/

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        int maxvalid = 0, lastright = -1;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') st.push(i);
            else {  // ')'
                if (!st.empty()) {
                    st.pop();
                    if (st.empty()) maxvalid = max(maxvalid, i-lastright);
                    else maxvalid = max(maxvalid, i-st.top());
                } else lastright = i;
            }
        }
        return maxvalid;
    }
};
